package leetcode.offer_two_special.queue;

import leetcode.tree.common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author mazouri
 * @create 2021-09-11 20:08
 */
public class _46_rightSideView {
    public List<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.offer(root);
        while (!q1.isEmpty()) {
            TreeNode node = q1.poll();

            if (node.left != null) q2.offer(node.left);
            if (node.right != null) q2.offer(node.right);
            //既然为空了，说明这一层已经遍历完了，最后一个节点就是最右边的节点
            if (q1.isEmpty()) {
                res.add(node.val);
                q1 = q2;
                q2 = new LinkedList<>();
            }
        }
        return res;
    }
}
